//
// Created by francklinson on 2021/7/8.
//

//给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。
//
//子数组 是数组的一段连续部分。
#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

class Solution {
public:
    /**
     * 前缀和+ hash
     * @param nums
     * @param goal
     * @return
     */
    int numSubarraysWithSum(vector<int> &nums, int goal) {
        int sum = 0;
        unordered_map<int, int> count; // hash记录 前缀和为x的有多少个
        int ans = 0;
        for (auto &x:nums) {
            ++count[sum];  // 更新hash
            sum += x; // 更新前缀和
            ans += count[sum - goal]; //在hash中找符合要求的结果
        }
        return ans;

    }
};

class Solution2 { /// 滑动窗口法
public:
    int numSubarraysWithSum(vector<int> &nums, int goal) {
        int n = nums.size();
        int left1 = 0, left2 = 0, right = 0;
        int sum1 = 0, sum2 = 0;
        int ret = 0;
        while (right < n) {
            sum1 += nums[right];
            while (left1 <= right && sum1 > goal) {
                sum1 -= nums[left1];
                left1++;
            }
            sum2 += nums[right];
            while (left2 <= right && sum2 >= goal) {
                sum2 -= nums[left2];
                left2++;
            }
            ret += left2 - left1; /// 两个指针内的都符合要求
            right++;
        }
        return ret;
    }
};

int main() {
    vector<int> nums{1, 0, 1, 0, 1};
    Solution sol;
    cout << sol.numSubarraysWithSum(nums, 2) << endl;
    return 0;
}